We propose a clinical trial evaluating the safety and bio-efficacy of recombinant vaccinia-PSA in the treatment of PSA recurrence following radical prostatectomy. The trial is based on preliminary data from the Principal Investigator, as well as reports published by others demonstrating the pre-clinical efficacy of recombinant vaccines for prostate cancer. The proposed trial is unique from other cancer vaccine trials in focusing on microscopic post-prostatectomy recurrence and in using concurrent androgen deprivation to minimize tumor volume and prostate-specific immunological tolerance/anergy. This study will supersede all other clinical trials for PSA recurrence following radical prostatectomy at our institution. The hypothesis of the proposed clinical trial is that anti-tumor activity of vaccinia-PSA (the study drug, a recombinant vaccine designed to activate T cells which specifically eliminate PSA-expressing prostate cancer cells) can be induced most effectively by: a) Reducing immunological anergy and tolerance signals associated with expression of PSA in normal prostate cells, and b) Minimizing tumor burden via surgery and androgen deprivation to further optimize vaccine efficacy. This hypothesis will be evaluated by a clinical study addressing three objectives. The first objective is to evaluate the safety of vaccinia-PSA administered via intradermal injection in patients with serological recurrence of prostate cancer after prior radical prostatectomy. The second objective is to evaluate the immunological effects of vaccinia-PSA in patients receiving this vaccine therapy. The third aim is to evaluate anti-tumor bioefficacy as measured by serum PSA measurement. Although other Phase I clinical trial using vaccinia-PSA are also underway, the focus on evaluating immunological and serological efficacy at the MTD and the use of androgen deprivation to reduce immunological anergy to PSA in this study are unique.